{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Arithmetic Subarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: checkArithmeticSubarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #等差子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>如果一个数列由至少两个元素组成，且每两个连续元素之间的差值都相同，那么这个序列就是 <strong>等差数列</strong> 。更正式地，数列 <code>s</code> 是等差数列，只需要满足：对于每个有效的 <code>i</code> ， <code>s[i+1] - s[i] == s[1] - s[0]</code> 都成立。</p>\n",
    "\n",
    "<p>例如，下面这些都是 <strong>等差数列</strong> ：</p>\n",
    "\n",
    "<pre>1, 3, 5, 7, 9\n",
    "7, 7, 7, 7\n",
    "3, -1, -5, -9</pre>\n",
    "\n",
    "<p>下面的数列 <strong>不是等差数列</strong> ：</p>\n",
    "\n",
    "<pre>1, 1, 2, 5, 7</pre>\n",
    "\n",
    "<p>给你一个由 <code>n</code> 个整数组成的数组 <code>nums</code>，和两个由 <code>m</code> 个整数组成的数组 <code>l</code> 和 <code>r</code>，后两个数组表示 <code>m</code> 组范围查询，其中第 <code>i</code> 个查询对应范围 <code>[l[i], r[i]]</code> 。所有数组的下标都是 <strong>从 0 开始</strong> 的。</p>\n",
    "\n",
    "<p>返回<em> </em><code>boolean</code> 元素构成的答案列表 <code>answer</code> 。如果子数组 <code>nums[l[i]], nums[l[i]+1], ... , nums[r[i]]</code> 可以 <strong>重新排列</strong> 形成 <strong>等差数列</strong> ，<code>answer[i]</code> 的值就是 <code>true</code>；否则<code>answer[i]</code> 的值就是 <code>false</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = <code>[4,6,5,9,3,7]</code>, l = <code>[0,0,2]</code>, r = <code>[2,3,5]</code>\n",
    "<strong>输出：</strong><code>[true,false,true]</code>\n",
    "<strong>解释：</strong>\n",
    "第 0 个查询，对应子数组 [4,6,5] 。可以重新排列为等差数列 [6,5,4] 。\n",
    "第 1 个查询，对应子数组 [4,6,5,9] 。无法重新排列形成等差数列。\n",
    "第 2 个查询，对应子数组 <code>[5,9,3,7] 。</code>可以重新排列为等差数列 <code>[3,5,7,9] 。</code></pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [-12,-9,-3,-12,-6,15,20,-25,-20,-15,-10], l = [0,1,6,4,8,7], r = [4,4,9,7,9,10]\n",
    "<strong>输出：</strong>[false,true,false,false,true,true]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>m == l.length</code></li>\n",
    "\t<li><code>m == r.length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 500</code></li>\n",
    "\t<li><code>1 &lt;= m &lt;= 500</code></li>\n",
    "\t<li><code>0 &lt;= l[i] &lt; r[i] &lt; n</code></li>\n",
    "\t<li><code>-10<sup>5</sup> &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [arithmetic-subarrays](https://leetcode.cn/problems/arithmetic-subarrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [arithmetic-subarrays](https://leetcode.cn/problems/arithmetic-subarrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,6,5,9,3,7]\\n[0,0,2]\\n[2,3,5]', '[-12,-9,-3,-12,-6,15,20,-25,-20,-15,-10]\\n[0,1,6,4,8,7]\\n[4,4,9,7,9,10]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        ans = []\n",
    "        for (l,r) in zip(l,r):\n",
    "            sub_arr = nums[l:r+1]\n",
    "            # print(sub_arr)\n",
    "            n = len(sub_arr)\n",
    "            sub_sum = sum(sub_arr)\n",
    "            max_v, min_v = max(sub_arr), min(sub_arr)\n",
    "            if (max_v-min_v)%(n-1) != 0:\n",
    "                ans.append(False)\n",
    "            elif sub_sum != n*(max_v+min_v)//2:\n",
    "                ans.append(False)\n",
    "            else:\n",
    "                d = (max_v-min_v)//(n-1)\n",
    "                record = False\n",
    "                if d != 0:\n",
    "                    zero_flag = False\n",
    "                    for v in sub_arr:\n",
    "                        if v == min_v:\n",
    "                            if zero_flag:\n",
    "                                ans.append(False)\n",
    "                                record = True\n",
    "                                break\n",
    "                            else:\n",
    "                                zero_flag = True\n",
    "\n",
    "                        if (v-min_v) %d != 0:\n",
    "                            ans.append(False)\n",
    "                            record = True\n",
    "                            break\n",
    "                if not record:\n",
    "                    ans.append(True)\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        n = len(nums)\n",
    "        m = len(l)\n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            L, R = l[i], r[i]\n",
    "            t = nums[L:R+1]\n",
    "            t.sort()\n",
    "            ok = True\n",
    "            for j in range(1, len(t) - 1):\n",
    "                if t[j] - t[j - 1] != t[j + 1] - t[j]:\n",
    "                    ok = False\n",
    "            if ok:\n",
    "                ans.append(True)\n",
    "            else:\n",
    "                ans.append(False)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        def check(nums, l, r):\n",
    "            n = r - l + 1\n",
    "            s = set(nums[l: l + n])\n",
    "            a1, an = min(nums[l: l + n]), max(nums[l: l + n])\n",
    "            d, mod = divmod(an - a1, n - 1)\n",
    "            return mod == 0 and all((a1 + (i - 1) * d) in s for i in range(1, n))\n",
    "        \n",
    "        return [check(nums, left, right) for left, right in zip(l, r)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        ans = list()\n",
    "        for left, right in zip(l, r):\n",
    "            minv = min(nums[left:right+1])\n",
    "            maxv = max(nums[left:right+1])\n",
    "            \n",
    "            if minv == maxv:\n",
    "                ans.append(True)\n",
    "                continue\n",
    "            if (maxv - minv) % (right - left) != 0:\n",
    "                ans.append(False)\n",
    "                continue\n",
    "            \n",
    "            d = (maxv - minv) // (right - left)\n",
    "            flag = True\n",
    "            seen = set()\n",
    "            for j in range(left, right + 1):\n",
    "                if (nums[j] - minv) % d != 0:\n",
    "                    flag = False\n",
    "                    break\n",
    "                t = (nums[j] - minv) // d\n",
    "                if t in seen:\n",
    "                    flag = False\n",
    "                    break\n",
    "                seen.add(t)\n",
    "            ans.append(flag)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        res=[]\n",
    "        for i,j in zip(l,r):\n",
    "            sub_nums=sorted(nums[i:j+1])\n",
    "            diff=sub_nums[1]-sub_nums[0]\n",
    "            res.append(all(diff==m-n for n,m in pairwise(sub_nums)))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        def check(nums, l, r):\n",
    "            n = r - l + 1\n",
    "            s = set(nums[l: l + n])\n",
    "            a1, an = min(nums[l: l + n]), max(nums[l: l + n])\n",
    "            d, mod = divmod(an - a1, n - 1)\n",
    "            return mod == 0 and all((a1 + (i - 1) * d) in s for i in range(1, n))\n",
    "        \n",
    "        return [check(nums, left, right) for left, right in zip(l, r)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        n = len(nums)\n",
    "        m = len(l)\n",
    "        ans = [False] * m\n",
    "        for i in range(m):\n",
    "            if r[i] - l[i] < 2:\n",
    "                ans[i] = True\n",
    "                continue\n",
    "            tmp = nums[l[i]:r[i] + 1]\n",
    "            tmp.sort()\n",
    "            diff = tmp[1] - tmp[0]\n",
    "            flag = True\n",
    "            for j in range(2, len(tmp)):\n",
    "                if tmp[j] - tmp[j - 1] != diff:\n",
    "                    flag = False\n",
    "                    break\n",
    "            ans[i] = flag\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 方法二：无排序、多次遍历 + 枚举\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        def check(arr: List[int]) -> bool:\n",
    "            mx, mi, st = -inf, inf, set()\n",
    "            for v in arr:\n",
    "                mx, mi = max(mx, v), min(mi, v)\n",
    "                st.add(v)\n",
    "            if (mx-mi) % (len(arr)-1) != 0:\n",
    "                return False\n",
    "            diff = (mx-mi) // (len(arr)-1)\n",
    "            # 坑：ValueError: range() arg 3 must not be zero\n",
    "            if diff == 0:\n",
    "                return True\n",
    "            for v in range(mi, mx+diff, diff):\n",
    "                if v not in st:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        ans = list()\n",
    "        for i in range(len(l)):\n",
    "            arr = nums[l[i] : r[i]+1]\n",
    "            ans.append(check(arr))\n",
    "        return ans\n",
    "\n",
    "\n",
    "# 方法一：排序\n",
    "# O(m.nlogn), O(n+logn)=O(n), 辅助变量arr占用n\n",
    "# class Solution:\n",
    "#     def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "#         def check(arr: List[int]) -> bool:\n",
    "#             arr.sort()\n",
    "#             diff = arr[1] - arr[0]\n",
    "#             for i in range(2, len(arr)):\n",
    "#                 if arr[i] - arr[i-1] != diff:\n",
    "#                     return False\n",
    "#             return True\n",
    "\n",
    "#         ans = list()\n",
    "#         for i in range(len(l)):\n",
    "#             arr = nums[l[i] : r[i]+1]\n",
    "#             ans.append(check(arr))\n",
    "#         return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        def check(arr):\n",
    "            arr.sort()\n",
    "            # print(arr)\n",
    "            n = arr.__len__()\n",
    "            if n <= 1:\n",
    "                return False\n",
    "            diff = arr[1] - arr[0]\n",
    "            for i in range(2, n):\n",
    "                if arr[i] - arr[i-1] != diff:\n",
    "                    return False\n",
    "            return True\n",
    "        ans = []\n",
    "        m = l.__len__()\n",
    "        for i in range(m):\n",
    "            if check(nums[l[i]:r[i]+1]):\n",
    "                ans.append(True)\n",
    "            else:\n",
    "                ans.append(False)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        def check(i, j):\n",
    "            arr = sorted(nums[i:j+1][:])\n",
    "            diff = arr[1] - arr[0]\n",
    "            for k in range(1, len(arr) - 1):\n",
    "                if arr[k + 1] - arr[k] != diff:\n",
    "                    return False\n",
    "            return True\n",
    "        ans = []\n",
    "        for i in range(len(l)):\n",
    "            if check(l[i], r[i]):\n",
    "                ans.append(True)\n",
    "            else:\n",
    "                ans.append(False)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "\n",
    "        for le, ri in zip(l, r):\n",
    "            t = sorted(nums[le : ri + 1])\n",
    "            if len(t) < 2:\n",
    "                res.append(False)\n",
    "                continue\n",
    "            flag = True\n",
    "            for i in range(2, len(t)):\n",
    "                if t[i] - t[i - 1] != t[i - 1] - t[i - 2]:\n",
    "                    flag = False\n",
    "                    res.append(False)\n",
    "                    break\n",
    "            if flag:\n",
    "                res.append(True)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        def check(nums, l, r):\n",
    "            n = r - l + 1\n",
    "            s = set(nums[l: l + n])\n",
    "            a1, an = min(nums[l: l + n]), max(nums[l: l + n])\n",
    "            d, mod = divmod(an - a1, n - 1)\n",
    "            return mod == 0 and all((a1 + (i - 1) * d) in s for i in range(1, n))\n",
    "        \n",
    "        return [check(nums, left, right) for left, right in zip(l, r)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        # indexes = [i for i in range(len(nums))]\n",
    "        # indexes.sort(key=lambda x: nums[x])\n",
    "        # index2index = {j: i for i, j in enumerate(indexes)}\n",
    "        ans = []\n",
    "        for left, right in zip(l, r):\n",
    "            sub_nums = copy.deepcopy(nums[left:right+1])\n",
    "            n = len(sub_nums)\n",
    "            for i in range(n):\n",
    "                for j in range(i+1, n):\n",
    "                    if sub_nums[j] > sub_nums[i]:\n",
    "                        sub_nums[i], sub_nums[j] = sub_nums[j], sub_nums[i]\n",
    "                if i == 1:\n",
    "                    diff = sub_nums[0] - sub_nums[1]\n",
    "                elif i > 1 and diff != sub_nums[i-1] - sub_nums[i]:\n",
    "                    ans.append(False)\n",
    "                    break\n",
    "            else:\n",
    "                ans.append(True)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        ans = list()\n",
    "        for left, right in zip(l, r):\n",
    "            minv = min(nums[left:right+1])\n",
    "            maxv = max(nums[left:right+1])\n",
    "            \n",
    "            if minv == maxv:\n",
    "                ans.append(True)\n",
    "                continue\n",
    "            if (maxv - minv) % (right - left) != 0:\n",
    "                ans.append(False)\n",
    "                continue\n",
    "            \n",
    "            d = (maxv - minv) // (right - left)\n",
    "            flag = True\n",
    "            seen = set()\n",
    "            for j in range(left, right + 1):\n",
    "                if (nums[j] - minv) % d != 0:\n",
    "                    flag = False\n",
    "                    break\n",
    "                t = (nums[j] - minv) // d\n",
    "                if t in seen:\n",
    "                    flag = False\n",
    "                    break\n",
    "                seen.add(t)\n",
    "            ans.append(flag)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        res = []\n",
    "        for left, right in zip(l, r):\n",
    "            s = nums[left: right + 1]\n",
    "            s.sort()\n",
    "            t = [s[i] - s[i - 1] for i in range(1, len(s))]\n",
    "            if len(set(t)) == 1:\n",
    "                res.append(bool(1))\n",
    "            else:\n",
    "                res.append(bool(0))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        def checkArithmetic(l):\n",
    "            s = sorted(l)\n",
    "            start = s[1] - s[0]\n",
    "            for x, y in pairwise(s[1:]):\n",
    "                if y - x != start:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        ans = []\n",
    "        for i, j in zip(l, r):\n",
    "            ans.append(checkArithmetic(nums[i:j+1]))\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        # ans = []\n",
    "        # for left, right in zip(l, r):\n",
    "        #     sub_nums = copy.deepcopy(nums[left:right+1])\n",
    "        #     n = len(sub_nums)\n",
    "        #     for i in range(n):\n",
    "        #         for j in range(i+1, n):\n",
    "        #             if sub_nums[j] > sub_nums[i]:\n",
    "        #                 sub_nums[i], sub_nums[j] = sub_nums[j], sub_nums[i]\n",
    "        #         if i == 1:\n",
    "        #             diff = sub_nums[0] - sub_nums[1]\n",
    "        #         elif i > 1 and diff != sub_nums[i-1] - sub_nums[i]:\n",
    "        #             ans.append(False)\n",
    "        #             break\n",
    "        #     else:\n",
    "        #         ans.append(True)\n",
    "        # return ans\n",
    "\n",
    "        # ans = list()\n",
    "        # for left, right in zip(l, r):\n",
    "        #     minv = min(nums[left:right+1])\n",
    "        #     maxv = max(nums[left:right+1])\n",
    "            \n",
    "        #     if minv == maxv:\n",
    "        #         ans.append(True)\n",
    "        #         continue\n",
    "        #     if (maxv - minv) % (right - left) != 0:\n",
    "        #         ans.append(False)\n",
    "        #         continue\n",
    "            \n",
    "        #     d = (maxv - minv) // (right - left)\n",
    "        #     flag = True\n",
    "        #     seen = set()\n",
    "        #     for j in range(left, right + 1):\n",
    "        #         if (nums[j] - minv) % d != 0:\n",
    "        #             flag = False\n",
    "        #             break\n",
    "        #         t = (nums[j] - minv) // d\n",
    "        #         if t in seen:\n",
    "        #             flag = False\n",
    "        #             break\n",
    "        #         seen.add(t)\n",
    "        #     ans.append(flag)\n",
    "        \n",
    "        # return ans\n",
    "\n",
    "        def check(nums, l, r):\n",
    "            n = r - l + 1\n",
    "            s = set(nums[l: l + n])\n",
    "            a1, an = min(nums[l: l + n]), max(nums[l: l + n])\n",
    "            d, mod = divmod(an - a1, n - 1)\n",
    "            return mod == 0 and all((a1 + (i - 1) * d) in s for i in range(1, n))\n",
    "        \n",
    "        return [check(nums, left, right) for left, right in zip(l, r)]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        def check(nums, l, r):\n",
    "            n = r - l + 1\n",
    "            s = set(nums[l: l + n])\n",
    "            a1, an = min(nums[l: l + n]), max(nums[l: l + n])\n",
    "            d, mod = divmod(an - a1, n - 1)\n",
    "            return mod == 0 and all((a1 + (i - 1) * d) in s for i in range(1, n))\n",
    "        \n",
    "        return [check(nums, left, right) for left, right in zip(l, r)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        res = []\n",
    "        for i, j in zip(l, r):\n",
    "            sub_nums = sorted(nums[i : j + 1])\n",
    "            diff = sub_nums[1] - sub_nums[0]\n",
    "            res.append(all(diff == m - n for n, m in pairwise(sub_nums)))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        list = []\n",
    "        for i in range(len(l)):\n",
    "            temp = nums[l[i]:r[i]+1]\n",
    "            temp.sort()\n",
    "            tmp1 = []\n",
    "            for z in range(len(temp)-1):\n",
    "                tmp1.append(temp[z+1]-temp[z])\n",
    "            num = len(set(tmp1))\n",
    "            if num==1:\n",
    "                list.append(True)\n",
    "            else:\n",
    "                list.append(False)\n",
    "        return list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def checkArithmetic(l):\n",
    "    s = sorted(l)\n",
    "    start = s[1] - s[0]\n",
    "    for x, y in pairwise(s[1:]):\n",
    "        if y - x != start:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "\n",
    "\n",
    "        return [checkArithmetic(nums[i:j+1]) for i, j in zip(l, r)]\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def is_re_Equidistant_sequence(self,t_list):\n",
    "        t_list.sort()\n",
    "        #print(t_list)\n",
    "        if len(t_list)<=2:\n",
    "            return True\n",
    "        pre_cha = t_list[1]-t_list[0]\n",
    "        for i,d in enumerate(t_list):\n",
    "            if i<1:\n",
    "                continue\n",
    "            if t_list[i]-t_list[i-1]!=pre_cha:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        res = []\n",
    "        for left,right in zip(l,r):\n",
    "            t_list = nums[left:right+1].copy()\n",
    "            if self.is_re_Equidistant_sequence(t_list):\n",
    "                res.append(True)\n",
    "            else:\n",
    "                res.append(False)\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        list = []\n",
    "        for i in range(len(l)):\n",
    "            tmp = [j+l[i] for j in range(r[i]-l[i]+1)]\n",
    "            temp = []\n",
    "            for k in tmp:\n",
    "                temp.append(nums[k])\n",
    "            temp.sort()\n",
    "            tmp1 = []\n",
    "            for z in range(len(temp)-1):\n",
    "                tmp1.append(temp[z+1]-temp[z])\n",
    "            num = len(set(tmp1))\n",
    "            if num==1:\n",
    "                list.append(True)\n",
    "            else:\n",
    "                list.append(False)\n",
    "        return list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        def is_sequence(nums):\n",
    "            length=len(nums)\n",
    "            if length==2:\n",
    "                return True\n",
    "            nums.sort()\n",
    "            tmp=nums[1]-nums[0]\n",
    "            for i in range(2,length):\n",
    "                if tmp!=nums[i]-nums[i-1]:\n",
    "                    return False\n",
    "            return True\n",
    "        n=len(nums)\n",
    "        output=[]\n",
    "        for x,y in zip(l,r):\n",
    "            if is_sequence(nums[x:y+1]):\n",
    "                output.append(True)\n",
    "            else:\n",
    "                output.append(False)\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        def equal_diff(nums):\n",
    "            if len(nums) == 2: return True\n",
    "            nums.sort()\n",
    "            diff = nums[1] - nums[0]\n",
    "            for i in range(2, len(nums)):\n",
    "                if nums[i] - nums[i-1] != diff:\n",
    "                    return False\n",
    "            return True\n",
    "        ans = []\n",
    "        for i in range(len(l)):\n",
    "            ans.append(equal_diff(nums[l[i]:r[i] + 1]))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        res=[]\n",
    "        for i in range(len(l)):\n",
    "            if r[i]-l[i]==1:\n",
    "                res+=[True]\n",
    "                continue\n",
    "            A=nums[l[i]:r[i]+1]\n",
    "            A.sort()\n",
    "            j=1\n",
    "            a=A[1]-A[0]\n",
    "            while j<=r[i]-l[i]-1 and A[j+1]-A[j]==a:\n",
    "                j+=1\n",
    "            if j==r[i]-l[i]:\n",
    "                res+=[True]\n",
    "            else:\n",
    "                res+=[False]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        ans = []\n",
    "        def check(arr):\n",
    "            interval = arr[1] - arr[0]\n",
    "            for i in range(len(arr) - 1):\n",
    "                if arr[i+1] -arr[i] != interval:\n",
    "                    return False\n",
    "            return True\n",
    "        for i in range(len(l)):\n",
    "            left, right = l[i], r[i]\n",
    "            arr= nums[left:right + 1]\n",
    "            arr.sort()\n",
    "            ans.append(check(arr))\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        def is_sequence(nums):\n",
    "            nums.sort()\n",
    "            length=len(nums)\n",
    "            if length==2:\n",
    "                return True\n",
    "            tmp=nums[1]-nums[0]\n",
    "            for i in range(2,length):\n",
    "                if tmp!=nums[i]-nums[i-1]:\n",
    "                    return False\n",
    "            return True\n",
    "        output=[]\n",
    "        for x,y in zip(l,r):\n",
    "            if is_sequence(nums[x:y+1]):\n",
    "                output.append(True)\n",
    "            else:\n",
    "                output.append(False)\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        n = len(l)\n",
    "        ans = []\n",
    "        for x, y in zip(l, r):\n",
    "            t = nums[x:y+1]\n",
    "            t.sort()\n",
    "            diff = None\n",
    "            flag = True\n",
    "            for a, b in pairwise(t):\n",
    "                if diff != None and b - a != diff:\n",
    "                    flag = False\n",
    "                    break\n",
    "                diff = b - a\n",
    "            ans.append(flag)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        def check(i, j):\n",
    "            arr = sorted(nums[i:j+1][:])\n",
    "            diff = arr[1] - arr[0]\n",
    "            for k in range(len(arr) - 1):\n",
    "                if arr[k + 1] - arr[k] != diff:\n",
    "                    return False\n",
    "            return True\n",
    "        ans = []\n",
    "        for i in range(len(l)):\n",
    "            if check(l[i], r[i]):\n",
    "                ans.append(True)\n",
    "            else:\n",
    "                ans.append(False)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        n = len(nums)\n",
    "        def check(subnums):\n",
    "            l = 0\n",
    "            minnum = float('inf')\n",
    "            maxnum = float('-inf')\n",
    "            for num in subnums:\n",
    "                minnum = min(minnum, num)\n",
    "                maxnum = max(maxnum, num)\n",
    "                l += 1\n",
    "            if((maxnum - minnum) % (l-1) != 0):\n",
    "                return False\n",
    "            if(maxnum == minnum):\n",
    "                return True\n",
    "            d = (maxnum - minnum) // (l-1)\n",
    "            book = [0]*l \n",
    "            for num in subnums:\n",
    "                if((num - minnum) % d != 0):\n",
    "                    return False\n",
    "                t = (num - minnum) // d\n",
    "                if(book[t] == 1):\n",
    "                    return False\n",
    "                book[t] = 1\n",
    "            return True\n",
    "\n",
    "        result = []\n",
    "        for i, j in zip(l, r):\n",
    "            subnums = nums[i:j+1]\n",
    "            result.append(check(subnums))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        def isArithmetic(arr):\n",
    "            arr.sort()\n",
    "            if len(arr) == 2:\n",
    "                return True\n",
    "            if all(arr[i+1] - arr[i] == arr[1]-arr[0] for i in range(len(arr) - 1)):\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        n = len(l)\n",
    "        res = [False] * n \n",
    "        for i in range(n):\n",
    "            if isArithmetic(nums[l[i]:r[i] + 1]):\n",
    "                res[i] = True\n",
    "            else:\n",
    "                res[i] = False\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        n = len(r)\n",
    "        ans = [False] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            t = sorted(nums[l[i]:r[i] + 1])\n",
    "            d = t[1] - t[0]\n",
    "            flag = True\n",
    "            for j in range(1, len(t)):\n",
    "                if t[j] - t[j -1] != d:\n",
    "                    flag = False\n",
    "                    break\n",
    "            ans[i] = flag\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        ret = [False]*len(l)\n",
    "        for i in range(len(l)):\n",
    "            flag = 0\n",
    "            cur = sorted(nums[l[i]:r[i]+1])\n",
    "            cha = cur[-1]-cur[-2]\n",
    "            for j in range(len(cur)-1,0,-1):\n",
    "                if cha != cur[j]-cur[j-1]:\n",
    "                    ret[i] = False\n",
    "                    flag = 1\n",
    "                    break\n",
    "            if not flag:\n",
    "                ret[i] = True\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\r\n",
    "        ans = []\r\n",
    "        for left, right in zip(l, r):\r\n",
    "            mx = max(nums[left:right+1])\r\n",
    "            mn = min(nums[left:right+1])\r\n",
    "            if mx == mn: # 全部相等\r\n",
    "                ans.append(True)\r\n",
    "                continue\r\n",
    "            if (mx-mn) % (right-left) != 0: # 公差不為整數\r\n",
    "                ans.append(False)\r\n",
    "                continue\r\n",
    "            d = (mx-mn) // (right-left) # 公差\r\n",
    "            flag = True\r\n",
    "            for i, num in enumerate(sorted(nums[left:right+1])):\r\n",
    "                if num != mn + d * i:\r\n",
    "                    flag = False\r\n",
    "                    break\r\n",
    "            ans.append(flag)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n",
    "        re=[]\n",
    "        for i,j in zip(l,r):\n",
    "            array= nums[i:j+1]\n",
    "            re.append(self.identify(array))\n",
    "        return re \n",
    "    def identify(self,array):\n",
    "        array.sort()\n",
    "        narray=[array[i+1]-array[i] for i in range(len(array)-1)]\n",
    "        if len(list(set(narray)))!=1:\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
